package cn.itcast.com.MyArrayList;

import java.io.ObjectInputStream;
import java.util.*;

public class MyArrayList<E> implements Mylist<E> {
    //存放数据的数组
    private Object[] elements;

    //当前集合里数据的实际个数
    private int size;

    //记录集合的结构发生变化的数据
    private int modCount;

    //默认长度
    private static final int DEFAULT_CAPACITY = 10;

    //由于某些虚拟机会占用8个字节的存储空间，并且数据容量是整形类型的，

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


    @Override
    public String toString() {
        StringBuilder stringBuilder=new StringBuilder();
        //[]

        stringBuilder.append("[");

        if (size>0){

            for (int i=0;i<size-1;i++){

                stringBuilder.append(elements[i]+",");

            }
            stringBuilder.append(elements[size-1]+"");
        }


        stringBuilder.append("]");

        return  stringBuilder.toString();

    }
    public MyArrayList() {
        //默认情况下ArrayList的初始大小
        elements = new Object[DEFAULT_CAPACITY];
    }

    //指定容量的构造方法
    /*
    * @param capacity  用户指定容量
    *
    */

    public MyArrayList(int capacity) {
        //默认情况下ArrayList的初始大小
        //参数的合法性校验是必须做的
        if (capacity<0 || capacity> Integer.MAX_VALUE-8){
            throw new IllegalArgumentException("capacity="+capacity);
        }
        elements = new Object[capacity];
    }

    /*
     * @param e 待添加的元素
     * @return true 添加成功
     */
    @Override
    public boolean add(E e) {
        add(size,e);

        return true;
    }

    /*
    * 把指定的元素element，添加到列表的指定索引位置
    * @param index 指定索引位置
    * @param element 指定元素
     */
    @Override
    public void add(int index, E element) {
        //参数的合法性校验 0 - size
        checkIndexForAdd(index);

        //考虑扩容
        //我们需要最少的容量
        int miniCapacity = size+1;
        //判断是否需要扩容，如果需要计算出合适的扩容大小
        if (miniCapacity > elements.length){
            //计算合适的扩容大小
            int newlength = caculateCapacity(miniCapacity);
            //扩容
            grow(newlength);
        }


        //腾出位置
        for (int i = size -1; i >= index; i--){
            elements[i + 1] = elements[i];
        }
        //将指定元素放到数组
        elements[index] = element;

        //收尾工作
        size++;    //实际容量++
        modCount++;//结构改变

    }

    ///扩容
    private void grow(int newLength) {
        //申请一个新的数组内存
        Object[] newData = new Object[newLength];

        //把之前的元素放入新的数组
        for (int i = 0; i < size; i++) {
            newData[i] = elements[i];
        }

        //指向新的数组，垃圾回收会处理掉之前的
        elements = newData;
    }

    //计算扩容大小
    private int caculateCapacity(int miniCapacity) {
        int newCapacity = elements.length + elements.length >> 1;
        //判断是否溢出
        if (newCapacity < 0||newCapacity > MAX_ARRAY_SIZE){
            newCapacity = MAX_ARRAY_SIZE;
        }
        //假如minniCapacity是MAX_ARRAY_SIZE+1怎么办
        return miniCapacity>newCapacity?miniCapacity:newCapacity;
    }

    //判断插入位置的合法性
    private void checkIndexForAdd(int index) {
        if (index<0||index > size){
            throw new IllegalArgumentException("index="+index);
        }
    }

    //清空集合的所有元素
    @Override
    public void clear() {
        //将所有的元素置为null
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        //收尾，size为0 modcount改变
        size = 0;
        modCount++;
    }

    //检查集合是否含有指定元素
    @Override
    public boolean contains(Object o) {
        //通过indexOf方法在集合中查找元素
        int i = indexOf(o);
        if (i == -1){
            return false;
        }else {
            return true;
        }
    }

    //查找指定索引位置的元素，并返回这个元素
    @Override
    public E get(int index) {
        //判断传入参数的合法性
        checkIndexForGet(index);

        return (E) elements[index];
    }

    //判断传入参数的合法性
    private void checkIndexForGet(int index) {
        if (index<0||index > size-1){
            throw new IllegalArgumentException("index="+index);
        }
    }

    //查找指定元素在集合中第一次出现的位置
    //-1表示没有该元素
    @Override
    public int indexOf(Object o) {

        if (o == null){
            for (int i = 0; i < size; i++) {
                if (o == elements[i]){
                    return i;
                }
            }
        }else {
            for (int i = 0; i < size; i++) {
                if (o.equals(elements[i])){
                    return i;
                }
            }
        }
        return -1;
    }
    //返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。
    //从后往前遍历即可
    @Override
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size - 1; i > 0; i--) {
                if (o == elements[i]){
                    return i;
                }
            }
        }else {
            for (int i = size - 1; i > 0; i--) {
                if (o.equals(elements[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    //判断集合是否为空
    @Override
    public boolean isEmpty() {
        return size==0;
    }

    //移除指定索引位置的元素
    @Override
    public E remove(int index) {
        //检查合法性
        checkIndexForGet(index);
        //拿到即将抛出的元素e
        E e = (E) elements[index];

        //在index-1之后的元素前移
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i+1];
        }

        //最后一个置null
        elements[size-1]=null;

        //收尾
        size--;
        modCount++;
        return e;
    }

    //删除在列表中第一个出现的元素
    //可以使用indexof方法找到位置

    @Override
    public boolean remove(Object o) {
        int i = indexOf(o);
        //如果不为空就执行remove方法
        if (i != -1){
            remove(i);
            return true;
        }
        return false;
    }

    //将列表中指定索引位置的元素替换为指定元素,返回被替换的元素
    @Override
    public E set(int index, E element) {
        //检查合法性
        checkIndexForGet(index);
        //存储要被替换的元素
        E e = (E) elements[index];
        elements[index] = element;

        return e;
    }

    @Override
    public int size() {
        return size;
    }


    //无参构造方法
    @Override
    public ListIterator<E> listIterator() {

        return new MyListIterator();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return new MyListIterator(index);
    }

    public class MyListIterator implements ListIterator<E>{

        //游标
        private int cursor;

        //记录next previous方法返回的元素的索引值
        private int lastRet = -1;

        //通过集合上的modCount来创建expectModCount，这代表着迭代器要修改的位置
        private int expectModCount = modCount;

        //无参构造

        public MyListIterator() {
        }

        //带cursor位置的构造方法

        public MyListIterator(int cursor) {
            //判断cursor的合法性
            if (cursor < 0 || cursor > size){
                throw new IllegalArgumentException("Cursor+"+cursor);
            }
            this.cursor = cursor;
        }

        //检查是否还有下一个元素，有则true，无则false
        @Override
        public boolean hasNext() {
            //游标到了尾部即size则表示没有下一个元素
            return cursor<size;
        }


        //获取游标的下一个元素，并返回它
        @Override
        public E next() {
            checkConcurrentModification();

            //先判断是否有下一个元素
            if (hasNext()){
                //根据cursor获得元素
                E e = (E) elements[cursor];

                lastRet =cursor;
                cursor++;
                return e;
            }else {
                throw new NoSuchElementException();
            }
        }

        //判断是否会导致并发修改异常
        private void checkConcurrentModification() {

            if (expectModCount!=modCount){
                throw  new ConcurrentModificationException();
            }
        }

        //检查cursor之前是否还有元素
        @Override
        public boolean hasPrevious() {
            return cursor > 0;
        }

        //获得cursor之前的那个元素
        @Override
        public E previous() {
            //检查并发
            checkConcurrentModification();
            //判断之前是否元素
            if (hasPrevious()){
                E e = (E) elements[cursor -1];
                cursor--;
                lastRet = cursor;

                return e;
            }else {
                throw new NoSuchElementException();
            }
        }

        //返回对next下一次调用的索引值
        @Override
        public int nextIndex() {
            return cursor;
        }

        //返回对previous下一次调用的索引值
        @Override
        public int previousIndex() {
            return cursor-1;
        }

        @Override
        public void remove() {
            if (lastRet == -1){
                throw new IllegalStateException("lastRet=-1");
            }
            //检查并发
            checkConcurrentModification();

            //通过lastRet进行删除操作
            MyArrayList.this.remove(lastRet);

            //少了一个元素，改变cursor
            cursor = lastRet;

            //只能进行一次删除
            lastRet = -1;
            //mylist remove方法改变了modcount、
            expectModCount = modCount;
        }

        //将当前光标指向的值修改为e
        @Override
        public void set(E e) {
            //等于-1表示无法修改
            if (lastRet == -1){
                throw new IllegalStateException("lastRet=-1");
            }
            //检查并发
            checkConcurrentModification();
            //调用外部类的set方法
            MyArrayList.this.set(lastRet,e);
        }

        @Override
        public void add(E e) {

            //检查并发
            checkConcurrentModification();
            //先调用外部类的add方法添加元素
            MyArrayList.this.add(cursor,e);

            //增加元素，cursor后移
            cursor++;
            //迭代器本身增加不会引发并发修改异常
            //add改变之后，modcount也改变了
            expectModCount = modCount;

            //将lastRet置为-1，防止通过这个位置进行迭代器那个remove操作
            lastRet=-1;
        }
    }
}
